package main

import "fmt"

// 1895. 最大的幻方
// 一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，
// 且每一行、每一列以及两条对角线的和 全部相等 。
// 幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

// 给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

// 方法1：暴力遍历
// 从左上向右下探索，判断对角线之和和第一行的和是否相等；或者从最大size的开始
func largestMagicSquare(grid [][]int) int {
	// 使用前缀和优化
	m, n := len(grid), len(grid[0])
	rowSum := make([][]int, m+1)
	colSum := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		rowSum[i] = make([]int, n+1)
		colSum[i] = make([]int, n+1)
	}
	for i := 1; i < m+1; i++ {
		for j := 1; j < n+1; j++ {
			rowSum[i][j] = rowSum[i][j-1] + grid[i-1][j-1]
			colSum[i][j] = colSum[i-1][j] + grid[i-1][j-1]
		}
	}

	// 从大到小枚举边长 edge
	var edge int = m
	if m > n {
		edge = n
	}
	for ; edge >= 1; edge-- {
		// 枚举正方形的左上角位置 (i,j)
		for i := 0; i+edge < m; i++ {
			for j := 0; j+edge < n; j++ {
				// 计算每一行、列、对角线的值应该是多少（以第一行为样本）
				var stdsum = rowSum[i][j+edge-1]
				if j != 0 {
					stdsum -= rowSum[i][j-1] // 减去见面若干像
				}

				check := true
				// 枚举每一行并用前缀和直接求和
				// 由于我们已经拿第一行作为样本了，这里可以跳过第一行
				for ii := i + 1; ii < i+edge; ii++ {
					var curRowSum = rowSum[i][j+edge-1]
					if j != 0 {
						curRowSum -= rowSum[ii][j-1]
					}
					if curRowSum != stdsum {
						check = false
						break
					}
				}
				if !check {
					continue
				}
				// 枚举每一列并用前缀和直接求和
				for jj := j; jj < j+edge; jj++ {
					var curColSum = colSum[i+edge-1][jj]
					if i != 0 {
						curColSum -= colSum[i-1][jj]
					}
					if curColSum != stdsum {
						check = false
						break
					}
				}
				if !check {
					continue
				}
				// d1 和 d2 分别表示两条对角线的和
				// 这里 d 表示 diagonal
				d1, d2 := 0, 0
				// 不使用前缀和，直接遍历求和
				for k := 0; k < edge; k++ {
					d1 += grid[i+k][j+k]
					d2 += grid[i+k][j+edge-1-k]
				}
				if d1 == stdsum && d2 == stdsum {
					return edge
				}
			}
		}
	}
	return edge
}

func main() {
	grid := [][]int{{7, 1, 4, 5, 6}, {2, 5, 1, 6, 4}, {1, 5, 4, 3, 2}, {1, 2, 7, 3, 4}}
	res := largestMagicSquare(grid)
	fmt.Println(res)
}
